package com.algorithm.排序.基于计数的排序;

import com.algorithm.排序.Sort;

//基于计数的排序，只能针对整数进行排序
/**
 * 这个版本的实现存在以下问题
 * 无法对负整数进行排序
 * 极其浪费内存空间
 * 是个不稳定的排序
 */
@SuppressWarnings("all")
public class 计数排序 extends Sort<Integer> {
    @Override
    protected void sort() {
        //找出最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
        }
        //开辟内存空间，存储每个整数出现的次数
        int[] counts = new int[max + 1];
        //统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i]] ++;
        }

        //根据整数出现的次数，对整数进行排序
        //遍历 counts
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i]-- > 0){
                //将counts[]数组的索引赋值给 array[]
                array[index++] = i;
            }
        }
    }
}